package zisu.algorithm.algorithm.LinkedList;

/**
 * @Author: 蔡翔
 * @Date: 2019/12/4 16:06
 * @Version 1.0
 */
public class LinkedList<E> {
    //结点--内部类。
    private class Node{

        private E e;

        private Node next;

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", next=" + next +
                    '}';
        }
    }

    private Node dummyHead;
    private Integer size;

    public LinkedList(){
        dummyHead = new Node(null,null);
        size = 0;
    }

    //获取链表个数
    public Integer getSize(){
        return size;
    }

    //判断是否为空
    public Boolean isEmpty(){
        return 0==size;
    }

    //在链表头 添加新元素e。
    public void addFirst(E e){
        addIndex(e,0);
    }

    //往index 节点之前插入 e
    //在链表的index (0-based)位置添加新的元素e
    public void addIndex(E e,Integer index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("add fail , Illegal index");
        }

        Node pre = dummyHead;
        for(int i=0;i<index;i++){
            pre = pre.next;
        }

        pre.next = new Node(e,pre.next);
        size++;
    }

    //往链表末尾添加 元素
    public void addLast(E e){
        addIndex(e,size);
    }

    //获取链表index位置元素
    public E getIndex(Integer index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("add fail , Illegal index");
        }
        Node pre = dummyHead;
        for(int i= 0;i<index;i++){
            pre = pre.next;
        }
        return pre.next.e;
    }

    public E getFirst(){
        return getIndex(0);
    }

    public E getLast(){
        return getIndex(size);
    }

    public void set(int index,E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("add fail , Illegal index");
        }
        Node pre = dummyHead;
        for(int i= 0;i<index;i++){
            pre = pre.next;
        }
        pre.next.e = e;
    }

    public boolean contains(E e){
        Node cur = dummyHead.next;
        while (cur!=null){
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public E remove(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("remove fail , Illegal index");
        }
        Node pre = dummyHead;
        for(int i = 0 ; i < index ; i++){
            pre = pre.next;
        }
        Node delNode = pre.next;
        pre.next = delNode.next;
        delNode.next = null;
        size--;
        return delNode.e;
    }

    public E removeFirst(){
        return remove(0);
    }

    public E removeLast(){
        return remove(size-1);
    }


    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("LinkedList : [ ");
        Node cur = dummyHead.next;
        while (cur!=null){
            str.append(cur.e+" -> ");
            cur = cur.next;
        }
        str.append("null ]");

        return str.toString();
    }


    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for(int i=0;i<5;i++){
            linkedList.addLast(i);
            System.out.println(linkedList);
        }
        linkedList.addIndex(11,2);

        linkedList.remove(2);
        linkedList.removeFirst();
        linkedList.removeLast();
        System.out.println(linkedList);

    }
}